300C - Beautiful Numbers - CodeForces Solution

//
// Created by Lapland on 2022/10/18.
//


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn=1e6+5;
typedef long long ll;
const int mod=1e9+7;
ll f[maxn],ans;
ll quick(ll a,ll b)
{
    ll ans=1;
    a=a%mod;
    while(b!=0)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
ll C(int n,int m)
{
    if(n<m) return 0;
    return f[n]*quick(f[m],mod-2)%mod*quick(f[n-m],mod-2)%mod;
}
bool check(int n,int a,int b)
{
    while(n>0)
    {
        if(n%10!=a&&n%10!=b) return 0;
        n/=10;
    }
    return 1;
}
int main()
{
    int n,a,b;
    scanf("%d%d%d",&a,&b,&n);
    f[0]=1;
    for(int i=1;i<=n;++i) f[i]=(f[i-1]*i)%mod;
    for(int i=0;i<=n;++i)
        if(check(i*a+(n-i)*b,a,b)) ans=(ans+C(n,i))%mod;
    printf("%lld\n",ans);
}